擦除重复项和排序向量的最有效方法是什么？ |
您所在的位置：网站首页 › std list排序 › 擦除重复项和排序向量的最有效方法是什么？ |
|
Nate Kohl建议的标准方法，仅使用向量，排序+唯一： sort( vec.begin(), vec.end() ); vec.erase( unique( vec.begin(), vec.end() ), vec.end() );不适用于指针向量。 仔细看看this example on cplusplus.com。 在他们的示例中，移动到末尾的“所谓的副本”实际上显示为？(未定义的值)，因为那些“所谓的副本”有时是“额外的元素”，有时在原始向量中有“丢失的元素”。 在指向对象的指针向量上使用std::unique()时会出现问题(内存泄漏、从堆中读取数据不佳、重复释放，这会导致分段错误等)。 下面是我对这个问题的解决方案:用ptgi::unique()替换std::unique()。 请参阅下面的文件ptgi_unique.hpp： // ptgi::unique() // // Fix a problem in std::unique(), such that none of the original elts in the collection are lost or duplicate. // ptgi::unique() has the same interface as std::unique() // // There is the 2 argument version which calls the default operator== to compare elements. // // There is the 3 argument version, which you can pass a user defined functor for specialized comparison. // // ptgi::unique() is an improved version of std::unique() which doesn't looose any of the original data // in the collection, nor does it create duplicates. // // After ptgi::unique(), every old element in the original collection is still present in the re-ordered collection, // except that duplicates have been moved to a contiguous range [dupPosition, last) at the end. // // Thus on output: // [begin, dupPosition) range are unique elements. // [dupPosition, last) range are duplicates which can be removed. // where: // [] means inclusive, and // () means exclusive. // // In the original std::unique() non-duplicates at end are moved downward toward beginning. // In the improved ptgi:unique(), non-duplicates at end are swapped with duplicates near beginning. // // In addition if you have a collection of ptrs to objects, the regular std::unique() will loose memory, // and can possibly delete the same pointer multiple times (leading to SEGMENTATION VIOLATION on Linux machines) // but ptgi::unique() won't. Use valgrind(1) to find such memory leak problems!!! // // NOTE: IF you have a vector of pointers, that is, std::vector, then upon return from ptgi::unique() // you would normally do the following to get rid of the duplicate objects in the HEAP: // // // delete objects from HEAP // std::vector objects; // for (iter = dupPosition; iter != objects.end(); ++iter) // { // delete (*iter); // } // // // shrink the vector. But Object * pointers are NOT followed for duplicate deletes, this shrinks the vector.size()) // objects.erase(dupPosition, objects.end)); // // NOTE: But if you have a vector of objects, that is: std::vector, then upon return from ptgi::unique(), it // suffices to just call vector:erase(, as erase will automatically call delete on each object in the // [dupPosition, end) range for you: // // std::vector objects; // objects.erase(dupPosition, last); // //========================================================================================================== // Example of differences between std::unique() vs ptgi::unique(). // // Given: // int data[] = {10, 11, 21}; // // Given this functor: ArrayOfIntegersEqualByTen: // A functor which compares two integers a[i] and a[j] in an int a[] array, after division by 10: // // // given an int data[] array, remove consecutive duplicates from it. // // functor used for std::unique (BUGGY) or ptgi::unique(IMPROVED) // // // Two numbers equal if, when divided by 10 (integer division), the quotients are the same. // // Hence 50..59 are equal, 60..69 are equal, etc. // struct ArrayOfIntegersEqualByTen: public std::equal_to // { // bool operator() (const int& arg1, const int& arg2) const // { // return ((arg1/10) == (arg2/10)); // } // }; // // Now, if we call (problematic) std::unique( data, data+3, ArrayOfIntegersEqualByTen() ); // // TEST1: BEFORE UNIQ: 10,11,21 // TEST1: AFTER UNIQ: 10,21,21 // DUP_INX=2 // // PROBLEM: 11 is lost, and extra 21 has been added. // // More complicated example: // // TEST2: BEFORE UNIQ: 10,20,21,22,30,31,23,24,11 // TEST2: AFTER UNIQ: 10,20,30,23,11,31,23,24,11 // DUP_INX=5 // // Problem: 21 and 22 are deleted. // Problem: 11 and 23 are duplicated. // // // NOW if ptgi::unique is called instead of std::unique, both problems go away: // // DEBUG: TEST1: NEW_WAY=1 // TEST1: BEFORE UNIQ: 10,11,21 // TEST1: AFTER UNIQ: 10,21,11 // DUP_INX=2 // // DEBUG: TEST2: NEW_WAY=1 // TEST2: BEFORE UNIQ: 10,20,21,22,30,31,23,24,11 // TEST2: AFTER UNIQ: 10,20,30,23,11,31,22,24,21 // DUP_INX=5 // // @SEE: look at the "case study" below to understand which the last "AFTER UNIQ" results with that order: // TEST2: AFTER UNIQ: 10,20,30,23,11,31,22,24,21 // //========================================================================================================== // Case Study: how ptgi::unique() works: // Remember we "remove adjacent duplicates". // In this example, the input is NOT fully sorted when ptgi:unique() is called. // // I put | separatators, BEFORE UNIQ to illustrate this // 10 | 20,21,22 | 30,31 | 23,24 | 11 // // In example above, 20, 21, 22 are "same" since dividing by 10 gives 2 quotient. // And 30,31 are "same", since /10 quotient is 3. // And 23, 24 are same, since /10 quotient is 2. // And 11 is "group of one" by itself. // So there are 5 groups, but the 4th group (23, 24) happens to be equal to group 2 (20, 21, 22) // So there are 5 groups, and the 5th group (11) is equal to group 1 (10) // // R = result // F = first // // 10, 20, 21, 22, 30, 31, 23, 24, 11 // R F // // 10 is result, and first points to 20, and R != F (10 != 20) so bump R: // R // F // // Now we hits the "optimized out swap logic". // (avoid swap because R == F) // // // now bump F until R != F (integer division by 10) // 10, 20, 21, 22, 30, 31, 23, 24, 11 // R F // 20 == 21 in 10x // R F // 20 == 22 in 10x // R F // 20 != 30, so we do a swap of ++R and F // (Now first hits 21, 22, then finally 30, which is different than R, so we swap bump R to 21 and swap with 30) // 10, 20, 30, 22, 21, 31, 23, 24, 11 // after R & F swap (21 and 30) // R F // // 10, 20, 30, 22, 21, 31, 23, 24, 11 // R F // bump F to 31, but R and F are same (30 vs 31) // R F // bump F to 23, R != F, so swap ++R with F // 10, 20, 30, 22, 21, 31, 23, 24, 11 // R F // bump R to 22 // 10, 20, 30, 23, 21, 31, 22, 24, 11 // after the R & F swap (22 & 23 swap) // R F // will swap 22 and 23 // R F // bump F to 24, but R and F are same in 10x // R F // bump F, R != F, so swap ++R with F // R F // R and F are diff, so swap ++R with F (21 and 11) // 10, 20, 30, 23, 11, 31, 22, 24, 21 // R F // aftter swap of old 21 and 11 // R F // F now at last(), so loop terminates // R F // bump R by 1 to point to dupPostion (first duplicate in range) // // return R which now points to 31 //========================================================================================================== // NOTES: // 1) the #ifdef IMPROVED_STD_UNIQUE_ALGORITHM documents how we have modified the original std::unique(). // 2) I've heavily unit tested this code, including using valgrind(1), and it is *believed* to be 100% defect-free. // //========================================================================================================== // History: // 130201 dpb [email protected] created //========================================================================================================== #ifndef PTGI_UNIQUE_HPP #define PTGI_UNIQUE_HPP // Created to solve memory leak problems when calling std::unique() on a vector. // Memory leaks discovered with valgrind and unitTesting. #include // std::swap // instead of std::myUnique, call this instead, where arg3 is a function ptr // // like std::unique, it puts the dups at the end, but it uses swapping to preserve original // vector contents, to avoid memory leaks and duplicate pointers in vector. #ifdef IMPROVED_STD_UNIQUE_ALGORITHM #error the #ifdef for IMPROVED_STD_UNIQUE_ALGORITHM was defined previously.. Something is wrong. #endif #undef IMPROVED_STD_UNIQUE_ALGORITHM #define IMPROVED_STD_UNIQUE_ALGORITHM // similar to std::unique, except that this version swaps elements, to avoid // memory leaks, when vector contains pointers. // // Normally the input is sorted. // Normal std::unique: // 10 20 20 20 30 30 20 20 10 // a b c d e f g h i // // 10 20 30 20 10 | 30 20 20 10 // a b e g i f g h i // // Now GONE: c, d. // Now DUPS: g, i. // This causes memory leaks and segmenation faults due to duplicate deletes of same pointer! namespace ptgi { // Return the position of the first in range of duplicates moved to end of vector. // // uses operator== of class for comparison // // @param [first, last) is a range to find duplicates within. // // @return the dupPosition position, such that [dupPosition, end) are contiguous // duplicate elements. // IF all items are unique, then it would return last. // template ForwardIterator unique( ForwardIterator first, ForwardIterator last) { // compare iterators, not values if (first == last) return last; // remember the current item that we are looking at for uniqueness ForwardIterator result = first; // result is slow ptr where to store next unique item // first is fast ptr which is looking at all elts // the first iterator moves over all elements [begin+1, end). // while the current item (result) is the same as all elts // to the right, (first) keeps going, until you find a different // element pointed to by *first. At that time, we swap them. while (++first != last) { if (!(*result == *first)) { #ifdef IMPROVED_STD_UNIQUE_ALGORITHM // inc result, then swap *result and *first // THIS IS WHAT WE WANT TO DO. // BUT THIS COULD SWAP AN ELEMENT WITH ITSELF, UNCECESSARILY!!! // std::swap( *first, *(++result)); // BUT avoid swapping with itself when both iterators are the same ++result; if (result != first) std::swap( *first, *result); #else // original code found in std::unique() // copies unique down *(++result) = *first; #endif } } return ++result; } template ForwardIterator unique( ForwardIterator first, ForwardIterator last, BinaryPredicate pred) { if (first == last) return last; // remember the current item that we are looking at for uniqueness ForwardIterator result = first; while (++first != last) { if (!pred(*result,*first)) { #ifdef IMPROVED_STD_UNIQUE_ALGORITHM // inc result, then swap *result and *first // THIS COULD SWAP WITH ITSELF UNCECESSARILY // std::swap( *first, *(++result)); // // BUT avoid swapping with itself when both iterators are the same ++result; if (result != first) std::swap( *first, *result); #else // original code found in std::unique() // copies unique down // causes memory leaks, and duplicate ptrs // and uncessarily moves in place! *(++result) = *first; #endif } } return ++result; } // from now on, the #define is no longer needed, so get rid of it #undef IMPROVED_STD_UNIQUE_ALGORITHM } // end ptgi:: namespace #endif下面是我用来测试它的单元测试程序： // QUESTION: in test2, I had trouble getting one line to compile,which was caused by the declaration of operator() // in the equal_to Predicate. I'm not sure how to correctly resolve that issue. // Look for //OUT lines // // Make sure that NOTES in ptgi_unique.hpp are correct, in how we should "cleanup" duplicates // from both a vector (test1()) and vector (test2). // Run this with valgrind(1). // // In test2(), IF we use the call to std::unique(), we get this problem: // // [dbednar@ipeng8 TestSortRoutes]$ ./Main7 // TEST2: ORIG nums before UNIQUE: 10, 20, 21, 22, 30, 31, 23, 24, 11 // TEST2: modified nums AFTER UNIQUE: 10, 20, 30, 23, 11, 31, 23, 24, 11 // INFO: dupInx=5 // TEST2: uniq = 10 // TEST2: uniq = 20 // TEST2: uniq = 30 // TEST2: uniq = 33427744 // TEST2: uniq = 33427808 // Segmentation fault (core dumped) // // And if we run valgrind we seen various error about "read errors", "mismatched free", "definitely lost", etc. // // valgrind --leak-check=full ./Main7 // ==359== Memcheck, a memory error detector // ==359== Command: ./Main7 // ==359== Invalid read of size 4 // ==359== Invalid free() / delete / delete[] // ==359== HEAP SUMMARY: // ==359== in use at exit: 8 bytes in 2 blocks // ==359== LEAK SUMMARY: // ==359== definitely lost: 8 bytes in 2 blocks // But once we replace the call in test2() to use ptgi::unique(), all valgrind() error messages disappear. // // 130212 dpb [email protected] created // ========================================================================================================= #include // std::cout, std::cerr #include #include // std::vector #include // std::ostringstream #include // std::unique() #include // std::equal_to(), std::binary_function() #include // assert() MACRO #include "ptgi_unique.hpp" // ptgi::unique() // Integer is small "wrapper class" around a primitive int. // There is no SETTER, so Integer's are IMMUTABLE, just like in JAVA. class Integer { private: int num; public: // default CTOR: "Integer zero;" // COMPRENSIVE CTOR: "Integer five(5);" Integer( int num = 0 ) : num(num) { } // COPY CTOR Integer( const Integer& rhs) : num(rhs.num) { } // assignment, operator=, needs nothing special... since all data members are primitives // GETTER for 'num' data member // GETTER' are *always* const int getNum() const { return num; } // NO SETTER, because IMMUTABLE (similar to Java's Integer class) // @return "num" // NB: toString() should *always* be a const method // // NOTE: it is probably more efficient to call getNum() intead // of toString() when printing a number: // // BETTER to do this: // Integer five(5); // std::cout getNum()/10)); } }; void test1(); void test2(); void printIntegerStarVector( const std::string& msg, const std::vector& nums ); int main() { test1(); test2(); return 0; } // test1() uses a vector (namely vector), so there is no problem with memory loss void test1() { int data[] = { 10, 20, 21, 22, 30, 31, 23, 24, 11}; // turn C array into C++ vector std::vector nums(data, data+9); // arg3 is a functor IntegerVectorIterator dupPosition = ptgi::unique( nums.begin(), nums.end(), IntegerEqualByTen() ); nums.erase(dupPosition, nums.end()); nums.erase(nums.begin(), dupPosition); } //================================================================================== // test2() uses a vector, so after ptgi:unique(), we have to be careful in // how we eliminate the duplicate Integer objects stored in the heap. //================================================================================== void test2() { int data[] = { 10, 20, 21, 22, 30, 31, 23, 24, 11}; // turn C array into C++ vector of Integer* pointers std::vector nums; // put data[] integers into equivalent Integer* objects in HEAP for (int inx = 0; inx < 9; ++inx) { nums.push_back( new Integer(data[inx]) ); } // print the vector to stdout printIntegerStarVector( "TEST2: ORIG nums before UNIQUE", nums ); // arg3 is a functor #if 1 // corrected version which fixes SEGMENTATION FAULT and all memory leaks reported by valgrind(1) // I THINK we want to use new C++11 cbegin() and cend(),since the equal_to predicate is passed "Integer *&" // DID NOT COMPILE //OUT IntegerStarVectorIterator dupPosition = ptgi::unique( const_cast(nums.begin()), const_cast(nums.end()), IntegerEqualByTenPointer() ); // DID NOT COMPILE when equal_to predicate declared "Integer*& arg1, Integer*& arg2" //OUT IntegerStarVectorIterator dupPosition = ptgi::unique( const_cast(nums.begin()), const_cast(nums.end()), IntegerEqualByTenPointer() ); // okay when equal_to predicate declared "Integer* arg1, Integer* arg2" IntegerStarVectorIterator dupPosition = ptgi::unique(nums.begin(), nums.end(), IntegerEqualByTenPointer() ); #else // BUGGY version that causes SEGMENTATION FAULT and valgrind(1) errors IntegerStarVectorIterator dupPosition = std::unique( nums.begin(), nums.end(), IntegerEqualByTenPointer() ); #endif printIntegerStarVector( "TEST2: modified nums AFTER UNIQUE", nums ); int dupInx = dupPosition - nums.begin(); std::cout |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |